Eagles Nest BBS 8/Eagles_Nest_Mac_Collection_Disc_8.TOAST/Developer Tools⁄Additions/IntermediatC/Exam 2 #12/Exam 2.c

C/C++ Source or Header | 1990-11-15 | 4KB | 176 lines

/*

EXAM 2

The problem to be solved for this exam is to write the functions necessary to
use a linked list as a "stack" representation.  A stack is similar to a queue,
but with a queue, the waiting is on a first come, first served basis while on a
stack it is "first in, last out."  The next arrival to a stack always goes to
the head of the stack (not to the end).  When a value is removed from the stack,
it is always removed from the head.  It could turn out that a person waiting in
a stack for service would never get serviced because of constant arrivals of new
people, but a stack is not intended for human waiting lines.

The stack is to be composed of any number of links that are created and placed
at the head of a linked list.  Links are removed only from the head.

For this quiz, you may write all the functions in a single C file.

You must include this declaration in your file:

    typedef struct link
       {
       char letter;
       struct link * next;
       } link, * link_ptr;

and write a main() function that will accomplish the following:

    (1)    loop five times;  adding the letters 'a', 'b', 'c', 'd', 'e'
        to a stack pointed to by a regional variable called "stack"
    (2)    will test the stack just created to see if it is empty.
        If the test function returns true, then printf "empty stack"
        else printf "stack has entries".  (You know it is not empty,
        but test it anyway.)
    (3)    will printf "d is on stack" if the character 'd' is in one
        of the links in the stack.  (Of course, it will be, but test
        for it anyway.)
    (4)    will remove all the links from the stack
        and printf the characters in each link -- in this exam the
        output would be: e d c b a.

To support main() you must write the following functions:

    push:        to place a link at the head of the stack.  The link should
                contain a character passed to this function.

    pop:        to remove the top most link from the stack.  The function
                should return the character that was in the link.  If the
                stack is empty, return the null character.  Remember to free
                the link after removal.

    empty:        to return a boolean value indicating whether the stack
                is empty or not.

    in_stack:    to return a boolean value -- true if the character
                specified as the parameter is present anywhere
                on the stack.

*/


#include <stdio.h>
#include <stdlib.h>


#define LOOPS            5
#define FIRST_LETTER    'a'
#define D_CHAR            'd'
#define TRUE            0xff
#define FALSE            0x00


typedef struct link
   {
   char letter;
   struct link * next;
   } link, * link_ptr;


static link * head = NULL;


static void push(char value);
static char pop(void);
static char empty(void);
static char in_stack(char value);


main()
   {
   int i;
   char value;

   value = FIRST_LETTER;
   for (i=0; i<LOOPS; i++)
      push(value++);
   if (empty())
      printf("empty stack\n");
   else
      printf("stack has entries\n");
   if (in_stack(D_CHAR))
      printf("d is on stack\n");
   for (i=0; i<5; i++)
      printf("%c ", pop());
   }


static void push(char value)
   {
   link * new_link;

   new_link = (link *) malloc(1 * sizeof(link));
   new_link->letter = value;
   if (!head)
      {
      head = new_link;            /* the first element in the stack's next pointer */
      head->next = new_link;    /* always points to itself */
      }
   else
      {
      new_link->next = head;
      head = new_link;
      }
   }


static char pop(void)
   {
   link * delete_link;
   char value;

   if (!head)
      return 0;                    /* empty stack */
   if (head == head->next)        /* only 1 element on the stack */
      {
      value = head->letter;
      free(head);
      head = NULL;
      return value;
      }
   else                            /* more than 1 element on stack */
      {
      value = head->letter;
      delete_link = head;
      head = head->next;
      free(delete_link);
      return value;
      }
   }


static char empty(void)
   {
   if (!head)
      return TRUE;
   else
      return FALSE;
   }


static char in_stack(char value)
   {
   link * next_link;

   next_link = head;
   while (next_link != next_link->next)    /* loop until an element is found that points to */
      {                                    /* itself, this is the first element on the stack */
      if (next_link->letter == value)
         return TRUE;
      next_link = next_link->next;
      }
   if (next_link->letter == value)        /* check the first element of the stack */
      return TRUE;
   return FALSE;
   }